情報の表現 — 記号・符号化 ( その 2)
山本昌志
∗2007 年 10 月 24 日
概 要
ここでの主な内容は，情報の符号化と誤り検出・訂正についてである．
1 本日の学習内容
情報の表現の方法とデジタル化の基礎を学ぶ
ハミング距離の概念が分かる．
デジタル符号の圧縮の方法が分かる．
デジタル符号の検出と誤りの訂正が分かる．
教科書 [1] の pp.27–35 が本日の範囲である．
2 デジタル符号化
一般に，情報を記号によって表現することを符号化 (コード 化) と言う．表現されたものを符号 (コード ) と呼ぶ．情報を表す記号は，何を使っても良いが，整数を使うのが最も簡単であるし，コンピューターとの 相性も良い．特に，コンピューターでは 2 進数がもっとも扱いやすい．
2.1 デジタル符号化の事例
2.1.1 2
進数符号10 進数 2 進数で表す話である．しかし ，講義ではこのこの辺の話は，省略する．10 進数と 2 進数，16 進数の間の変換については，諸君はしつこく学習したであろう．私も，3 年生の電子計算機の第 2 回の講義
「位取り基数法 (2 進数，10 進数，16 進数)
1」で，説明した．よもや，これらの変換が分からない者など ，い ないはず．
ただし ，ハミング距離 (Hamming distance)
2については，述べておくべきであろう．
∗独立行政法人 秋田工業高等専門学校 電気情報工学科
1http://www.akita-nct.jp/yamamoto/lecture/2005/3E/2nd/html/index.html
2ハミングとは人の名前．初期のコンピューター(偶数パリティを使っていた)は誤りが多く，しばしば計算途中で止まった．これ に，腹を立てたハミングは，誤り訂正を考えたとか．
二つのデータで，同じ位置にあるビットで異なるビットの個数をハミング距離と呼ぶ．たとえば， (01000110) と (01000001) のハミング距離は 3 である．
8 ビット整数 (0–255) のうち，隣り合う整数の組でハミング距離が最大の組を示せ．
2.1.2
グレ イ符号グレ イ符号は，値が一つ異なる整数のハミング距離がいつでも 1 の符号である．教科書 [1] の pp.28 の 表 2.2 を見れば，このことが分かるだろう．詳細については，応用上，重要な話もあるが，今後の講義にあ まり関係なので，説明しない．
グレ イ符号については，私の講義ノート「グレ イコード 誤りの検出
3」に書いてあるので見ると良いだ ろう．また，参考文献 [2] も詳しい．
2.2 デジタル符号の圧縮
p の確率 (probability)で生じる事実が発生した時，それを観測することにより得られる情報量は − log
2P[bit]
である．たとえば，X 先生はテストの出題には癖があり，練習問題 A と B が出題される確率は表 1 のとお りである．両方の問題が出題された場合，それにより得られる情報量は 1[bit] である．
問題 B のみ出題されたとき，得られる情報量は何 [bit] か?
表を見て分かるとおり，これらの事実は 4 通りある．そのため， 2 桁の 2 進数で符号化可能である．しかし，
得られる情報量は 2 ビットとは限らない．
表 1: テストに練習問題 A と B が出題されるときの符号化と確率
問題 A と B の出題 ど ちらも出題されない 問題 B のみ 問題 A のみ 両方出題
符号化 00 01 10 11
確率 1/8 1/8 1/4 1/2
すなわちデジタル符号 (データ) の圧縮は，情報量 [bit] と 2 進数の桁数が異なることを利用する．すなわ ち，情報を 2 進数で符号化すると，その桁数と情報量は一般には異なる．先に示したように，符号化され た 2 進数の 0 と 1 の出現確率が異なるためである．もし ，0 と 1 の出現確率が同じ 1/2 ならば，桁数と情 報量は同じになり，デジタル符号の圧縮はできない．
実際の圧縮の例として，教科書 [1] の pp.30–31 ではハフマン符号化とラングレス圧縮の例が記述されて いる．
ハフマン符号化は，出現確率の大きな記号に短いビット列を，小さいに記号に長いビット列を当てる方法である．すべての記号に同じ長さのビット列を与えるよりも，短いビット列で符号化できる確率 が高い．
3http://akita-nct.jp/yamamoto/lecture/2003/2E/pdf files 2E/numerical code.pdf
ラングレス圧縮は，ビットの値とその繰り返しで符号化する．人間の感覚では気がつかない部分の情報を減らすことにより，デジタル符号を圧縮することも可能であ る．たとえば ，画像データフォーマットで使われる JPEG などがその例である．教科書 [1] の pp.27 の図 2.10 のように，周波数の高い成分の情報を削除しても人間は気がつかない．人間が気がつかない周波数の 高い成分を圧縮しても，人間への伝達は問題がない．
符号の圧縮には，可逆圧縮と非可逆圧縮がある．圧縮されたデジタル符号が元の状態に戻せるものを可逆 圧縮，戻せないものを非可逆圧縮と呼ぶ．ハフマン符号化とラングレス圧縮は可逆圧縮で，JPEG 圧縮は 非可逆圧縮である．
コーヒーブレ イク
¶ ³
TEX 関係で有名な奥村晴彦先生が，圧縮のジレンマとして，おもしろいことを書いている [3] ので引用 しておく．
定理
最悪の場合でも圧縮データが元データより大きくならない圧縮ソフトは，どんな データも圧縮できない．
証明
元データのサイズが 0 ビットなら，圧縮して大きくなることはないのだから，圧 縮データのサイズも 0 ビットでなくてはならい．元データのサイズが 1 ビットなら，もう 0 ビットは使用済みなので，圧縮データは 1 ビットでなくてはならない．1 ビットの元デー タ (2 通り) が，1:1 に対応する．以下同様に続けていけば ，元データのサイズが n ビット なら，圧縮しても n ビットでなければ成らないことがわかる．
要するに，元データと圧縮データは 1:1 に対応するため，全く圧縮できないことになる．また，もしこ の定理が成り立たなければ ，この圧縮ソフトを繰り返し使うことにより，どんなデータも 0 ビットに 圧縮できてしまう．これは，矛盾である．
µ ´
3 符号の誤り検出・訂正
この辺の話は，参考文献 [4] にかなりわかりやすく書かれている．余裕があると呼んでみると良い．
3.1 誤り検出と訂正がなぜ必要か ?
コンピューターでは大量のデータ，すなわち気の遠くなるような 0 と 1 のビット列が取り扱われており，
一つの間違いも許されない．諸君が使っているパソコンのメイン メモリーが 1G[byte] とすると，どれだけ のビットがあるだろうか? 8 × 2
30= 2
33' 10
10個のビットがある．100 億個である．ハードデ ィスクにな ると，その数百倍のビットを扱うことになる．
データのエラーは 2 通りの方法で生じる．一つは，メモリーやハードデ ィスクの製造時における欠陥で
ある．もう一つは，稼働時のおける書き込みあるいは読み込みの間違い，あるいはデータ保存時にビットが
変化してしまうことによるエラーである．
前者のエラー，製造時のエラーは欠陥部分を使わないようにしてしまうことにより回避できる．いつも，
同じ場所でエラーが生じるので，検査によりそのビットを使わないようにする．
ここで問題とするのは後者のエラーである．すなわち，装置に欠陥が無いものの，書き込んだものと異な る値が読み出される場合である．これは熱や宇宙線の作用により，記憶装置のビットが変化する場合に起き る．このようなビットの変化は，ランダムに生じ ，時や場所を特定することができない．
ランダムにビットが変化するようなエラーは，情報の保存のみならず，情報の伝達の時も生じる．情報を 伝達のケーブルの電圧を下げると熱振動によるノイズの影響によりビットが変化するかもしれない．また，
通信速度を上げると，パルス幅が短くなり，トランジスターが誤動作するかもしれない．
熱や宇宙線によるこれらのビットの変化が生じる確率は，ゼロでは無いが非常に少ない．問題の無いレベ ルになるように，記憶装置や通信装置を慎重に設計を行わなければならない．ただ，ゼロにすることは不可 能なので，ビットが変化しても情報が失われないように，データ蓄積と転送のとき工夫する．
データ蓄積と転送は全く異なる技術に見えるが，ランダムにビットが変化するエラーを防ぐ ためには同 じような技術が使える．
3.2 誤りの検出
パリティビットを使うと，蓄えた情報あるいは転送して送られてきた情報の誤りの有無が分かる．たとえ ば，0110010 と符号化された情報があるとする．これの最後に 1 ビット付け加えて，列の全体の 1 の数を 偶数
4にする．すなわち，01100101 とする．このようにパリティビットを加えて，符号を記憶，あるいは 転送する．
データを読み出すときに，1 の数を数えれば誤りの有無が分かる．もし ，何らかの原因でどれか一つの ビットが反転した場合，全体の 1 の数は奇数となるので，おかしいと気付く．
この方法だと，二つのビットの誤り (二重誤り) には気付かない．どのようにすれば，二重あるいは 3 重 の誤りが分かるだろうか?
偶数パリティを加えることにより，正しい符号のハミング距離は 2 以上になる．パリティビットを含んだ 符号全体の 1 の数は，いつも偶数であるからである．従って，一つの誤りが生じると，正しい場合に比べ てハミング距離が 1 変化し，不当な符号になる．もし，2 重の誤りが生じると，正しい符号と区別がつかな くなる．従って，誤りの検出ができない．
このことを一般化すると，t 個の誤りを検出するためには，正しい符号のハミング距離を t + 1 以上にす る必要がある (図 1)．
4偶数にする場合を偶数パリティ，奇数にする場合を奇数パリティと呼ぶ．
ハミング距離 10
正しい符号 正しい符号
4ビットの誤り
図 1: 誤りの検出限界とハミング距離の関係．
3.3 誤りの訂正
記憶装置の場合，誤りが分かっただけでは困る．データの損失になるからである．それに対して，通信の 場合は，再送信することにより，正しい情報を得ることができる．しかし，いずれの場合でも，誤りを検出 すると同時に得られた誤りのある符号から，正しい符号に訂正できれば，ハッピーである．これは，技術的 に可能である．
t 個のビットの誤りがある場合，ハミング距離が 2t + 1 以上ならば，誤りを検出して訂正までできる．こ のことを，図 2 を用いて説明する．この図，次のように理解する．
誤り検出・訂正用のビットを付加して，正しい符号のハミング距離を 11 としている．
もし，一個のビットに誤りがあると，元の正しい符号からハミング距離が 1 だけ離れた場所に符号が 移動する．この場合，最近接の正しい符号に戻せば，誤りの訂正を行ったことになる．
二個，三個，四個，五個までならば，最近接の正しい符号に戻すことができる．このように最近接の 正しい符号に戻すことにより誤りの訂正ができる．
もし，誤りが 6 個以上になると，最近接の正しい符号に戻しても，元の符号に戻らない．誤った訂正 を行ったことになり，情報が失われる．
ハミング距離 11 正しい
符号1
符号1に訂正
正しい 符号2
符号2に訂正
図 2: 誤りの訂正限界とハミング距離の関係．
実際に，誤りの訂正ができることを教科書のハミング符号で示す (図 3)．この教科書のハミング符号によ ると，以下のようなことが分かる．
もし ，得られた符号を検査して，z
1と z
2が間違いで，z
3が間違いの場合，教科書の表 2.3 より，x
1が間違いだと分かる．
もし ，得られた符号を検査して，z
1が間違いで，z
1と z
3が間違いの場合，教科書の表 2.3 より，y
1が間違いだと分かる．
ハミング符号による誤り訂正のおもしろいところは，付加したビットそのものの誤りも分かるところであ る．元の符号と訂正用に付加した符号は同等に取り扱われる．
実際に使われているハミング符号は，もっと高度なもので，高速に処理ができるようになっている．教科 書のハミング符号は，分かりやすく書くために書かれており，処理の効率は悪い．
0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 1
0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1
1 1 0 1 1 0 1 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1
x1 x2 x3 x4 y1 y2 y3
